package main

import "fmt"

/**
假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

解析:
利用二分查找(binary search)
将数组一分为二，其中一定有一个是有序的，另一个可能是有序，也可能是部分有序。
此时有序部分用二分法查找。无序部分再一分为二，其中一个一定有序，另一个可能
有序，可能无序。就这样循环.
第一种情况是左侧有序，即nums[start]<nums[mid],这种情况下如果target在nums[start]
与nums[mid]之间，end=mid，否则start=mid。缩小了查找范围，继续在start与end间查找
第二种情况是右侧有序，即nums[mid]<mid[end],这种情况下如果target在nums[mid]与num[end]
之间，start=mid,否则end=mid。缩小了查找范围，继续在start与end间查找
![](http://cdn.bsummer.cn/20191126023022.png)
https://www.youtube.com/watch?v=lWEIIFFflQY
*/

// 优秀 来自chat
func search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		} else if nums[mid] >= nums[left] {
			if target >= nums[left] && target < nums[mid] {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			if target <= nums[right] && target > nums[mid] {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return -1
}

//func search(nums []int, target int) int {
//	if len(nums) == 0 {
//		return -1
//	}
//
//	start, end := 0, len(nums)-1
//
//	// 注意循环条件1+start<j即最后在两者相邻时跳出循环，这么做是因为两者相邻后无法再继续缩小范围且会永远满足条件进入死循环（中间节点永远是两个节点中一个）
//	for start+1 < end {
//		mid := start + (end-start)/2  // 如果使用(start+mid)/2的话，start+mid有可能溢出
//		if nums[start] <= nums[mid] { // 确认图形形状
//			if target >= nums[start] && target <= nums[mid] { // 判断target所在位置
//				end = mid
//			} else {
//				start = mid
//			}
//		} else if nums[mid] < nums[end] {
//			if target >= nums[mid] && target <= nums[end] {
//				start = mid
//			} else {
//				end = mid
//			}
//		}
//	}
//
//	// 此时i 与 j相邻 start+1==end
//	if nums[start] == target {
//		return start
//	}
//
//	if nums[end] == target {
//		return end
//	}
//
//	return -1
//}

func main() {
	fmt.Println(search([]int{1, 3, 5}, 1))
}

func search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		m := left + (right-left)/2
		if target == nums[m] {
			return m
		} else if nums[m] >= nums[left] {
			if target >= nums[left] && target < nums[m] {
				right = m - 1
			} else {
				left = m + 1
			}
		} else {
			if target > nums[m] && target <= nums[right] {
				left = m + 1
			} else {
				right = m - 1
			}
		}
	}
	return -1
}
